package com.hjr.leetcode.question100;

import com.hjr.leetcode.util.entity.ListNode;

/**
 *21. 合并两个有序链表
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 */
public class q21 {

    public static void main(String[] args) {
        ListNode listNode = mergeTwoLists(new ListNode(-9, new ListNode(3)), new ListNode(5, new ListNode(7)));
        while (listNode != null){
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }

    // 快慢指针，谁小谁移动
    // 0ms 41mb
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }

        ListNode listNode = new ListNode();
        ListNode pre = listNode;
        while (list1 != null || list2 != null){
            if (list1 == null){
                listNode.next = list2;
                list2 = list2.next;
            }else if (list2 == null){
                listNode.next = list1;
                list1 = list1.next;
            }else {
                if (list1.val <= list2.val) {
                    listNode.next = list1;
                    list1 = list1.next;
                } else {
                    listNode.next = list2;
                    list2 = list2.next;
                }
            }
            listNode = listNode.next;
        }
        return pre.next;
    }
}
